With ever-increasing data size and transactions rates for online transaction processing (OLTP) applications, horizontally partitioning, or sharding, the database is a common technique to scale out the database to multiple servers in a shared-nothing architecture. To leverage the benefits of scale-out, effective partitioning techniques typically limit most transactions to a single server. However the design of effective partitioning techniques is challenging given the applications' complexity with hundreds of tables and transaction types. Existing techniques typically recommend a partitioning strategy that minimizes a percentage of distributed transactions in a workload, assuming that each transaction has a similar cost.